package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.WC;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

/**
 * @author tzp
 * @since 2020/9/27
 */
public class WC208_3 implements WC {
    public static class ThroneInheritance {
        public static class InherTreeNode {
            public String name;
            public boolean isDead = false;
            public LinkedList<InherTreeNode> child = new LinkedList<>();

            public InherTreeNode(String name) {
                this.name = name;
            }
        }

        public InherTreeNode root;
        public HashMap<String, InherTreeNode> members = new HashMap<>();


        public ThroneInheritance(String kingName) {
            this.root = new InherTreeNode(kingName);
            members.put(kingName, this.root);
        }

        public void birth(String parentName, String childName) {
            InherTreeNode current = new InherTreeNode(childName);
            InherTreeNode parent = members.get(parentName);
            parent.child.add(current);
            members.put(childName, current);
        }

        public void death(String name) {
            members.get(name).isDead = true;
        }

        public List<String> getInheritanceOrder() {
            ArrayList<String> result = new ArrayList<>();
            rec(root, result);
            return result;
        }

        private void rec(InherTreeNode current, ArrayList<String> result) {
            if (!current.isDead) {
                result.add(current.name);
            }
            for (int i = 0; i < current.child.size(); i++) {
                rec(current.child.get(i), result);
            }
        }
    }

    public static void main(String[] args) {
        String[] operations = new String[]{"ThroneInheritance", "birth", "birth", "birth", "birth", "birth", "birth", "getInheritanceOrder", "death", "getInheritanceOrder"};
        String[][] datas = new String[][]{
                {"king"}, {"king", "andy"}, {"king", "bob"},
                {"king", "catherine"}, {"andy", "matthew"}, {"bob", "alex"},
                {"bob", "asha"}, {null}, {"bob"}, {null}};

        ThroneInheritance obj = new ThroneInheritance(datas[0][0]);
        for (int i = 1; i < operations.length; i++) {
            switch (operations[i]) {
                case "birth": {
                    obj.birth(datas[i][0], datas[i][1]);
                    break;
                }
                case "death": {
                    obj.death(datas[i][0]);
                    break;
                }
                case "getInheritanceOrder": {
                    System.out.println(obj.getInheritanceOrder());
                    break;
                }
                default:
                    throw new RuntimeException();
            }
        }
    }
}
